package List$Stack$queue;

import common.ListNode;

/**
 * K 个一组反转链表
 */
public class ReverseNodesInKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode protectNode = new ListNode();
        protectNode.next = head;
        ListNode end = null;
        ListNode lastNode = protectNode;
        while (head != null) {
            // 找到k个元素的终止节点
            end = findEnd(head, k);
            if (end == null) {
                lastNode.next = head;
                break;
            }
            ListNode nextHead = end.next;
            // 上一组元素的终止节点指向该组元素反转后的起始节点（即找到的终止节点）
            lastNode.next = end;
            // 将k个元素执行反转
            reverseLink(head, end);
            lastNode = head;
            // 该组元素的终止节点指向下一组元素
            head = nextHead;
        }
        return protectNode.next;
    }

    private ListNode findEnd(ListNode head, int kk){
        ListNode e = head;
        // kk > 1 可以保证找到的是结尾节点
        while (e != null && kk > 1){
            e = e.next;
            kk--;
        }
        if (kk == 1) return e;
        return null;
    }

    private void reverseLink(ListNode head, ListNode end){
        if (head == end) return;
        ListNode lastNode = null;
        while (lastNode != end){
            ListNode temp = head.next;
            head.next = lastNode;
            lastNode = head;
            head = temp;
        }
    }
}
